package consistenthash

/*
Copyright 2013 Google Inc.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

     http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

// 环形一致性hash实现

import (
	"hash/crc32"
	"sort"
	"strconv"
)

type Hash func(data []byte) uint32

type Map struct {
	hash     Hash           // 使用的 Hash 函数
	replicas int            // 副本虚拟节点数, 用于解决少节点在环上分布不均匀的问题
	keys     []int          // 节点 hash 值排序
	hashMap  map[int]string // 节点 hash 值与节点信息的映射
}

func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		/* 没有指定 hash 函数时指定默认的函数 */
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

// IsEmpty Returns true if there are no items available.
func (m *Map) IsEmpty() bool {
	return len(m.keys) == 0
}

// Add Adds some keys to the hash.
func (m *Map) Add(keys ...string) {
	for _, key := range keys {
		for i := 0; i < m.replicas; i++ {
			// use replicas id + _ + key to avoid the key has pre-number.
			hash := int(m.hash([]byte(strconv.Itoa(i) + "_" + key)))
			if m.hashMap[hash] == "" {
				m.keys = append(m.keys, hash)
				m.hashMap[hash] = key
			}
		}
	}

	/* 对节点 hash 值进行排序,相当于顺时针的环 */
	sort.Ints(m.keys)
}

func (m *Map) Del(key string) {
	for i := 0; i < m.replicas; i++ {
		hash := int(m.hash([]byte(strconv.Itoa(i) + "_" + key)))
		for j := 0; j < len(m.keys); j++ {
			if m.keys[j] == hash {
				m.keys = append(m.keys[:j], m.keys[j+1:]...)
				break
			}
		}
		delete(m.hashMap, hash)
	}
}

// Get Gets the closest item in the hash to the provided key.
func (m *Map) Get(key string) string {
	if m.IsEmpty() {
		return ""
	}

	hash := int(m.hash([]byte(key)))

	// Binary search for appropriate replica.
	idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })

	// Means we have cycled back to the first replica.
	if idx == len(m.keys) {
		idx = 0
	}
	return m.hashMap[m.keys[idx]]
}
